package com.mjf.sort;

import java.util.*;

/**
 * 基数排序
 * <p>
 * 基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是通过键值的各个位的值，将要排序的元素分配至某些“桶”中，达到排序的作用
 * <p>
 * 基数排序法是属于稳定性的排序，基数排序法的是效率高的稳定性排序法
 * <p>
 * 基数排序(Radix Sort)是桶排序的扩展
 * <p>
 * 时间复杂度：
 * <p>
 * 空间复杂度：
 */
public class RadixSort {
    public static void main(String[] args) {

        int[] arr = {53, 3, 542, 748, 14, 214};
        System.out.println("排序前: " + Arrays.toString(arr));
        radixSort(arr);
        System.out.println("排序后: " + Arrays.toString(arr));

    }

    /**
     * 思路：
     * 第1轮排序  [按照个位排序]:
     * 说明： 事先准备10个数组(10个桶)， 0-9 分别对应 位数的 0-9
     * (1) 将 各个数，按照个位大小 放入到 对应的 各个数组中
     * (2)  然后从 0-9 个数组/桶，依次，按照加入元素的先后顺序取出
     * <p>
     * 第2轮排序  [按照十位排序]
     * ...
     * 依次类推
     */
    public static void radixSort(int[] arr) {
        // 元素最大位数
        int maxDigit = 0;
        // 桶（一维数组为桶编号，二维数组为桶中元素）
        int[][] buckets = new int[10][arr.length];

        // 获取元素最大位数
        for (int item : arr) {
            int itemLength = String.valueOf(item).length();
            if (itemLength > maxDigit) {
                maxDigit = itemLength;
            }
        }

        // 遍历元素最大位数次
        for (int i = 1; i <= maxDigit; i++) {
            // 记录每个桶中实际放了多少个元素
            int[] bucketItemCount = new int[10];
            // 将元素按对应位上的值放入各自桶中
            for (int item : arr) {
                // 桶编号(第一次遍历去元素的个位数，第二次十位数。。。)
                int bucketNo = item / (int) Math.pow(10, i - 1) % 10;
                // 将元素放入相应编号桶中
                buckets[bucketNo][bucketItemCount[bucketNo]] = item;
                // 相应编号桶的存放元素个数加1
                bucketItemCount[bucketNo] = bucketItemCount[bucketNo] + 1;
            }

            int x = 0;
            // 按桶编号从低到高取出桶中元素
            for (int y = 0; y < buckets.length; y++) {
                // 取出各桶中实际存放元素
                for (int z = 0; z < bucketItemCount[y]; z++) {
                    // 将桶中元素按桶编号从低到高放入原数组
                    arr[x++] = buckets[y][z];
                }
            }
        }
    }
}


